/**
 *  @file IsCircle.c
 *  @desc 判断一个双向链表是否存在环（使用快慢指针）
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-25
 *  @version 1.0
 */

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// 定义双向链表节点
typedef struct node {
    int data;
    struct node *next;
    struct node *pre;
} node, *link;

// 创建节点
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    newNode->pre = NULL;
    return newNode;
}

// 初始化头结点
void initNode(link *head) {
    link newNode = createNode(0);  // 头节点值一般为 0（占位）
    if (newNode == NULL) return;
    *head = newNode;
}

// 头插法
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = head->next;
    newNode->pre = head;
    if (head->next != NULL) {
        head->next->pre = newNode;
    }
    head->next = newNode;
}

// 尾插法
void istTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
    newNode->pre = cur;
}

// 打印链表（注意：有环会死循环）
void printList(link head) {
    if (head == NULL || head->next == NULL) return;
    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// 判断链表是否有环（Floyd 判圈法）
int isCircle(link head) {
    if (head == NULL || head->next == NULL) return 0;
    link slow = head;
    link fast = head->next;

    while (fast != NULL && fast->next != NULL) {
        if (fast == slow) {
            return 1;  // 有环
        }
        fast = fast->next->next;
        slow = slow->next;
    }

    return 0;  // 无环
}

int main() {
    link head = NULL;
    initNode(&head);

    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);

    printList(head);

    // 制造一个环：最后一个节点的 next 指向头节点，形成环
    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = head;     // 创建环
    head->pre = cur;      // 双向连接（可选，非必要）

    // 检测环
    if (isCircle(head)) {
        printf("have cycle\n");
    } else {
        printf("have't cycle\n");
    }

    return 0;
}
